Data communication systems are used to exchange information between devices. The information to be exchanged comprises data that is organized as strings of digital bits formatted so as to be recognizable by other devices and to permit the information to be processed and/or recovered.
The exchange of information may occur over a publically accessible network, such as a communication link between two devices, over a dedicated network within an organization, or may be between two devices within the same dedicated component, such as within a computer or point of sale device.
The devices may range from relatively large computer systems through to telecommunication devices, cellular phones, monitoring devices, sensors, electronic wallets and smart cards, and a wide variety of devices that are connected to transfer data between two or more of such devices.
A large number of communication protocols have been developed to allow the exchange of data between different devices. The communication protocols permit the exchange of data in a robust manner, often with error correction and error detection functionality, and for the data to be directed to the intended recipient and recovered for further use.
Because the data may be accessible to other devices, it is vulnerable to interception and observation or manipulation. The sensitive nature of the information requires that steps are taken to secure the information and ensure its integrity.
A number of techniques collectively referred to as encryption protocols and authentication protocols have been developed to provide the required attributes and ensure security and/or integrity in the exchange of information. These techniques utilize a key that is combined with the data.
There are two main types of cryptosystems that implement the protocols, symmetric key cryptosystems and asymmetric or public-key cryptosystems. In a symmetric key cryptosystem, the devices exchanging information share a common key that is known only to the devices intended to share the information. Symmetric key systems have the advantage that they are relatively fast and therefore able to process large quantities of data in a relatively short time, even with limited computing power. However, the keys must be distributed in a secure manner to the different devices, which leads to increased overhead and vulnerability if the key is compromised.
Public-key cryptosystems utilize a key pair, one of which is public and the other private, associated with each device. The public key and private key are related by a “hard” mathematical problem so that even if the public key and the underlying problem are known, the private key cannot be recovered in a feasible time. One such problem is the factoring of the product of two large primes, as utilized in RSA cryptosystems. Another is the discrete log problem in a finite cyclic group. A generator, α, of the underlying group is identified as a system parameter and a random integer, k, generated for use as a private key. To obtain a public key, K, a k-fold group operation is performed so that K=f(α,k).
Different groups may be used in discrete log cryptosystems including the multiplicative group of a finite field, the group of integers in a finite cyclic group of order p, usually denoted Zp* and consisting of the integers 0 to p−1. The group operation is multiplication so that K=f(αk).
Another group that is used for enhanced security is an elliptic curve group. The elliptic curve group consists of pairs of elements, one of which is designated x and the other y, in a field that satisfy the equation of the chosen elliptic curve. For a group of order p, the relationship would generally be defined by y2=x3+ax+b mod p. Other curves are used for different underlying fields. Each such pair of elements is a point on the curve, and a generator of the group or an appropriate subgroup is designated as a point P. The group operation is addition, so a private key k will have a corresponding public-key f(kP).
Public-key cryptosystems reduce the infrastructure necessary with symmetric key cryptosystems. A device generates a key pair by obtaining an integer k, which is used as a private key and performing a k-fold group operation to generate the corresponding public-key. In an elliptic curve group, this would be kP. The public-key is published so it is available to other devices.
Devices may then use the key pair in communications between them. If one device wishes to encrypt a message to be sent to another device, it uses the public key of the intended recipient in an encryption protocol. The message may be decrypted and recovered by the other device using the private key.
To assure the recipient of the integrity of a message, the device may also use the key pair in a digital signature protocol. The message is signed using the private key k and other devices can confirm the integrity of the message using the public key kP.
A digital signature is a computer readable data string (or number) which associates a message with the author of that data string. A digital signature generation algorithm is a method of producing digital signatures.
Digital signature schemes are designed to provide the digital counterpart to handwritten signatures (and more). A digital signature is a number dependent on some secret known only to the signer (the signer's private key), and, additionally, on the contents of the message being signed.
Signatures must be verifiable—if a dispute arises as to whether an entity signed a document, an unbiased third party should be able to resolve the matter equitably, without requiring access to the signer's private key. Disputes may arise when a signer tries to repudiate a signature it did create, or when a forger makes a fraudulent claim.
The three fundamental different types of signatures are:                A digital signature scheme with appendix, which requires the original message as input into the verification process.        A digital signature scheme with message recovery, which does not require the original message as input to the verification process. Typically the original message is recovered during verification.        A digital signature scheme with partial message recovery, which requires only a part of the message to be recovered.        
The present application is concerned with asymmetric digital signatures schemes with appendix. As discussed above, asymmetric means that each entity selects a key pair consisting of a private key and a related public key. The entity maintains the secrecy of the private key which it uses for signing messages, and makes authentic copies of its public key available to other entities which use it to verify signatures. Usually Appendix means that a cryptographic hash function is used to create a message digest of the message, and the signing transformation is applied to the message digest rather than to the message itself.
A digital signature must be secure if it is to fulfill its function of non-repudiation. Various types of attack are known against digital signatures. The types of attacks on Digital Signatures include:                Key-Only Attack: An adversary only has the public key of the signer.        Know Signature Attack: An adversary knows the public key of the signer and has message-signature pairs chosen and produced by the signer.        Chosen Message Attack: The adversary chooses messages that are signed by the signer, in this case the signer is acting as an oracle.        Attacks on digital signatures can result in the following breakages:        Total Break: An adversary is either able to compute the private key information of the signer, or finds an efficient alternate signing algorithm.        Selective Forgery: An adversary is able to create a valid signature for a particular message.        Existential Forgery: An adversary is able to forge a signature for at least one message.        Universal Forgery: An adversary can forge any message without the secret key.        
Ideally, a digital signature scheme should be existentially unforgeable under chosenmessage attack. This notion of security was introduced by Goldwasser, Micali and Rivest. Informally, it asserts that an adversary who is able to obtain the signatures of an entity for any messages of its choice is unable to forge successfully a signature of that entity on a single other message.
Digital signature schemes can be used to provide the following basic cryptographic services: data integrity (the assurance that data has not been altered by unauthorized or unknown means), data origin authentication (the assurance that the source of data is as claimed), and non-repudiation (the assurance that an entity cannot deny previous actions or commitments). Digital signature schemes are commonly used as primitives in cryptographic protocols that provide other services including entity authentication, authenticated key transport, and authenticated key agreement.
The digital signature schemes in use today can be classified according to the hard underlying mathematical problem which provides the basis for their security:
Integer Factorization (IF) schemes, which base their security on the intractability of the integer factorization problem. Examples of these include the RSA and Rabin signature schemes.
Discrete Logarithm (DL) schemes, which base their security on the intractability of the (ordinary) discrete logarithm problem in a finite field. Examples of these include the ElGamal, Schnorr, DSA, and Nyberg-Rueppel signature schemes.
Elliptic Curve (EC) schemes, which base their security on the intractability of the elliptic curve discrete logarithm problem.
One signature scheme in wide spread use is the elliptic curve digital signature algorithm (ECDSA). To generate the signature it is necessary to hash the message and generate a public session key from a random integer. One signature component is obtained by a modular reduction of one co-ordinate of the point representing the public session key, and the other signature component combines the hash and private keys of the signer. This requires inversion of the session private key, which may be relatively computationally intensive.
Verification requires the hashing of the message and inversion of the other component. Various mathematical techniques have been developed to make the signing and verification efficient, however the hashing and modular reduction remain computationally intensive.
It is an object of the present invention to provide a signature scheme in which the above disadvantages may be obviated or mitigated.